import java.util.*;

/**
 * 串连所有字符串
 * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/669370738/
 */
class Solution {
    public static List<Integer> findSubstring(String s, String[] words) {
        //预处理
        Map<String,Integer> hash1 = new HashMap<String,Integer>();

        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0) + 1);

        List<Integer> ret = new ArrayList<Integer>();

        int len = words[0].length(),n = words.length;

        //窗口
        for(int i = 0;i < len;i++){
            Map<String,Integer> hash2 = new HashMap<String,Integer>();
            for(int left = i,right = i,count = 0;right < s.length();right += len){
                //1.进入窗口
                String in;
                if(right + len <= s.length())
                  in = s.substring(right,right + len);
                else in = s.substring(right,s.length() -1);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;

                //判断
                if(right - left + 1 > len * n){
                    //出窗口
                    String out = s.substring(left,left + len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.getOrDefault(out,0) - 1);
                    left += len;
                }

                //3.更新
                if(count == n) ret.add(left);

            }
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(Solution.findSubstring("wordgoodgoodgoodbestword",
                new String[]{"word","good","best","good"}));
    }
}